package algorithm;

public class leetcode_0130 {
    public void solve(char[][] board) {
        int m=board.length;
        int n=board[0].length;
        char[][] result=new char[m][n];
        for(int i=0;i<n;++i){
            if(board[0][i]=='O'){
                dp(board,result,0,i,m,n);
            }
            if(board[m-1][i]=='O'){
                dp(board,result,m-1,i,m,n);
            }
        }
        for(int i=1;i<m-1;++i){
            if(board[i][0]=='O'){
                dp(board,result,i,0,m,n);
            }
            if(board[i][n-1]=='O'){
                dp(board,result,i,n-1,m,n);
            }
        }
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(result[i][j]!='O'){
                    result[i][j]='X';
                }
            }
        }
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                board[i][j]=result[i][j];
            }
        }
    }
    public void dp(char[][] board,char[][] result,int p,int q,int m,int n){
        if(p>=0&&p<m&&q>=0&&q<n&&board[p][q]=='O'&&result[p][q]!='O'){
            result[p][q]='O';
            dp(board,result,p-1,q,m,n);
            dp(board,result,p,q+1,m,n);
            dp(board,result,p+1,q,m,n);
            dp(board,result,p,q-1,m,n);
        }
    }
}
